package com.coder.algorithm.leetcode

import com.coder.algorithm.struct.ListNode

/**
 * [142. 环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/)
 *
 * @author yuhus
 * @date: 2022/3/31
 */
object l_0142 {
    /**
     * fast，slow 代表快慢指针
     * 当 fast == slow 时，两指针在环中 第一次相遇
     * 设：链表共有 a+b 个节点，其中 链表头部到链表入口 有 a 个节点（不计环入口节点）
     * 设：两指针分别走了 f，s 步，则有：
     *   1. f = 2s
     *   2. f = s + nb（解析：fast 比 slow 多走环的长度整数倍）
     * - 以上相减得 s = nb，f = 2nb
     * - 如果让指针从链表头部一直向前走并统计步数 K，那个所有走到环入口节点时的步数为：k = a + nb（n代表自然数，和上面的n数值不同）
     * - 目前 s = nb，在走 a 步就会到环的入口，
     */
    fun detectCycle(head: ListNode?): ListNode? {
        if (head == null) {
            return null
        }
        var slow = head
        var fast = head
        var count = 0
        while (fast != null) {
            if (fast == slow) {
                if (count == 1){
                    fast = head
                    while (fast != slow) {
                        slow = slow?.next
                        fast = fast?.next
                    }
                    return fast
                }
                count++
            }
            slow = slow?.next
            fast = fast.next?.next
        }
        return null
    }
}